package com.ryujung.array.leetcode_15;
/*
 * @lc app=leetcode.cn id=15 lang=java
 *
 * [15] 三数之和
 */

import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

// @lc code=start
class Solution {

    /**
     * q1：如何遍历各种组合 ? 方式一：暴力遍历，复杂度L：O(n^3); 方式二：首先排序，然后枚举不重复 且符合条件的三元素
     * 
     * q2：如何存储各种组合，保证不重复
     */
    public static List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> ans = new LinkedList<>();
        for (int i = 0; i < nums.length; i++) {
            if (i != 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            int k = nums.length - 1;
            for (int j = i + 1; j < nums.length; j++) {
                if (j != i + 1 && nums[j] == nums[j - 1]) {
                    continue;
                }

                while (j < k && nums[i] + nums[j] + nums[k] > 0) {
                    k--;
                }
                if (j == k) {
                    break;
                }
                if (nums[i] + nums[j] + nums[k] != 0) {
                    continue;
                } else {
                    LinkedList<Integer> list = new LinkedList<Integer>();
                    list.add(nums[i]);
                    list.add(nums[j]);
                    list.add(nums[k]);
                    ans.add(list);
                }
            }
        }
        return ans;
    }

    public static void main(String[] args) {
        System.out.println(threeSum(new int[] { -1, 0, 1, 2, -1, -4 }));
    }

}
// @lc code=end
